namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0701. 二叉搜索树中的插入操作")]
    public class No0701_InsertIntoBST : AbsBaseTestItem
    {
        /*
        给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
        注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
        提示：
            给定的树上的节点数介于 0 和 10^4 之间
            每个节点都有一个唯一整数值，取值范围从 0 到 10^8
            -10^8 <= val <= 10^8
            新值和原始二叉搜索树中的任意节点值都不同
        */
        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
            {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

        public override void OnTest()
        {
            Assert.TestExe(InsertIntoBST,
                new TreeNode(4)
                {
                    left = new TreeNode(2)
                    {
                        left = new TreeNode(1),
                        right = new TreeNode(3),
                    },
                    right = new TreeNode(7),
                }, 5,
                new TreeNode(4)
                {
                    left = new TreeNode(2)
                    {
                        left = new TreeNode(1),
                        right = new TreeNode(3),
                    },
                    right = new TreeNode(7)
                    {
                        left = new TreeNode(5),
                    },
                },
                new TreeNode(5)
                {
                    left = new TreeNode(2)
                    {
                        left = new TreeNode(1),
                        right = new TreeNode(3)
                        {
                            right = new TreeNode(5),
                        },
                    },
                    right = new TreeNode(7),
                });
        }

        public TreeNode InsertIntoBST(TreeNode root, int val)
        {
            if (root == null)
            {
                return new TreeNode(val);
            }
            TreeNode pos = root;
            while (pos != null)
            {
                if (val < pos.val)
                {
                    if (pos.left == null)
                    {
                        pos.left = new TreeNode(val);
                        break;
                    }
                    else
                    {
                        pos = pos.left;
                    }
                }
                else
                {
                    if (pos.right == null)
                    {
                        pos.right = new TreeNode(val);
                        break;
                    }
                    else
                    {
                        pos = pos.right;
                    }
                }
            }
            return root;
        }
    }
}
